/**
 * 重要：比较排序的下界是nlogn，如堆排序、归并排序等
 * 一些非比较排序如计数排序、桶排序等，通常需要一些先验条件
 */

#include "includes/mysort.h"


// =====================  比较排序 ========================= //

void fast_sort(void **arr, int len, cmp_t cmp) {
    if(len < 2) return;
    int cur = 0, i = 1;
    while(i < len) {
        if(cmp(arr[i], arr[cur]) < 0) {
            void *tmp = arr[i];
            arr_move_right(arr, cur, i - cur, 1);
            arr[cur] = tmp;
            cur++;
        }
        i++;
    }
    fast_sort(arr, cur, cmp);
    fast_sort(arr + cur + 1, len - cur - 1, cmp);
}

void merge_sort(void **arr, int len, cmp_t cmp) {
    if(len < 2) return;
    int mid = len / 2;
    merge_sort(arr, mid, cmp);
    merge_sort(arr + mid, len - mid, cmp);
    int i = 0, j = mid;
    while(i < j && j < len) {
        if(cmp(arr[j], arr[i]) < 0) {
            void *tmp = arr[j];
            arr_move_right(arr, i, j - i, 1);
            arr[i] = tmp;
            j++;
        }
        i++;
    }
    // printf("after merge data first: %d, last: %d\n", *(int *) arr[0], *(int *) arr[len - 1]);
}



// ===================== 线性时间排序 =========================== //

void counting_sort(int *arr, int len, int max, int *res) {
    int *arr_counting = malloc(sizeof(int) * (max + 1));
    for (int i = 0; i < max + 1; i++)
    {
        arr_counting[i] = 0;
    }
    for (int i = 0; i < len; i++)
    {
        arr_counting[arr[i]]++;
    }
    // 此时arr_counting[i]的值为arr中等于i的元素数量

    for (int i = 0; i < max; i++)
    {
        arr_counting[i+1] = arr_counting[i] + arr_counting[i + 1];
    }
    // 此时arr_counting[i]的值为arr中小于i的元素数量
    for (int i = 0; i < len; i++)
    {
        res[arr_counting[arr[i]] - 1] = arr[i];
        arr_counting[arr[i]]--;
    }
    
    free(arr_counting);
}
